Jansson and Sung showed that, given a dense set of input triplets T(representing hypotheses about the local evolutionary relationships of tripletsof species), it is possible to determine in polynomial time whether thereexists a level-1 network consistent with T, and if so to construct such anetwork. They also showed that, unlike in the case of trees (i.e. level-0networks), the problem becomes NP-hard when the input is non-dense. Here wefurther extend this work by showing that, when the set of input triplets isdense, the problem is even polynomial-time solvable for the construction oflevel-2 networks. This shows that, assuming density, it is tractable toconstruct plausible evolutionary histories from input triplets even when suchhistories are heavily non-tree like. This further strengthens the case for theuse of triplet-based methods in the construction of phylogenetic networks. Wealso show that, in the non-dense case, the level-2 problem remains NP-hard.
展开▼
